package algorithm.leetcode.medium;

/*
 给定一个单链表，把所有的奇数节点和偶数节点分别排在一起。
 注意，这里的奇数节点和偶数节点指的是节点编号的奇偶性，而不是节点的值的奇偶性。

 你的算法的空间复杂度应为 O(1)，时间复杂度应为 O(nodes)，nodes 为节点总数。
 */

/**
 * @author jack.wu
 * @version 1.0
 * @date 2020/12/31
 */
public class Question328 {

    public static void main(String[] args) {

    }

    public ListNode oddEvenList(ListNode head) {
        if (head == null || head.next == null || head.next.next == null) {
            return head;
        }
        ListNode res = head;
        ListNode evenHead = head.next;
        ListNode odd = head;
        ListNode even = head.next;
        // true:奇数 false:偶数
        boolean flg = true;
        head = head.next.next;
        while (head != null) {
            if (flg) {
                odd.next = head;
                odd = head;
            } else {
                even.next = head;
                even = head;
            }
            flg = !flg;
            head = head.next;
        }
        odd.next = evenHead;
        even.next = null;
        return res;
    }


    private static class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }
}
